import functools


class Solution(object):
    def maximizeSweetness(self, sweetness, k):
        """
        :type sweetness: List[int]
        :type k: int
        :rtype: int
        """

        def judge(value):
            max_value = float('inf')
            count = 0
            now_value = 0
            i = 0
            while i < n:
                now_value += sweetness[i]
                if now_value >= value:
                    max_value = min(now_value, max_value)
                    now_value = 0
                    count += 1
                i += 1
                if count == k:
                    break
            if i <= n - 1:
                max_value = min(max_value, sum(sweetness[i:]))
                if max_value >= value:
                    return max_value
                else:
                    return -1
            else:
                return -1
        if k == 0:
            return sum(sweetness)
        total = sum(sweetness) // (k + 1)
        n = len(sweetness)
        now_max = 0
        left = 0
        right = total
        while right > left:
            mid_value = (left + right) // 2
            now = judge(mid_value)
            if now > 0:
                now_max = max(now_max, now)
                left = mid_value + 1
            else:
                right = mid_value - 1
        if right == left:
            now_max = max(now_max, judge(left))
        return now_max


data = Solution()
sweetness = [1, 2, 3, 4, 5, 6, 7, 8, 9]
k = 5
print(data.maximizeSweetness(sweetness, k))
sweetness = [1, 2, 2, 1, 2, 2, 1, 2, 2]
k = 2
print(data.maximizeSweetness(sweetness, k))
sweetness = [5, 6, 7, 8, 9, 1, 2, 3, 4]
k = 8
print(data.maximizeSweetness(sweetness, k))
sweetness = [52832, 63820, 96186, 1623, 88717]
k = 3
print(data.maximizeSweetness(sweetness, k))
sweetness = [63820, 96186, 1623]
k = 1
print(data.maximizeSweetness(sweetness, k))
